package code1_100.code11_20;

import java.util.ArrayList;
import java.util.List;

/*
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
 */
public class Code14 {
//    /**
//     * 解法一
//     * @param strs
//     * @return
//     */
//    public String longestCommonPrefix(String[] strs) {
//        if(strs.length<=0)
//            return "";
//        if(strs.length==1)
//            return strs[0];
//        StringBuilder tag = new StringBuilder("");
//        int l=strs[0].length();
//        for (int i=0;i<strs.length-1;i++){
//            char[] ch1 = strs[i].toCharArray();
//            char[] ch2 = strs[i+1].toCharArray();
//            int len = Math.min(ch1.length,ch2.length);
//            int k =0;
//            while(k<len&&k<l){
//                if(ch1[k]!=ch2[k]){
//                    break;
//                }
//                tag.delete(k,k+1);
//                tag.insert(k,ch1[k]);
//                k++;
//            }
//            tag.delete(k,tag.length());
//            l = Math.min(l,k);
//        }
//        if (tag.length()!=0)
//            return tag.toString();
//        return "";
//    }


    //动态规划解法
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)
            return "";
        return longestCommonPrefix(strs,0,strs.length-1);

    }

    public String longestCommonPrefix(String[] strs,int lcpLeft,int lcpRight) {
        if(lcpLeft==lcpRight)
            return strs[lcpLeft];
        int mid = (lcpRight-lcpLeft)/2+lcpLeft;
        String left =  longestCommonPrefix(strs,lcpLeft,mid);
        String right = longestCommonPrefix(strs,mid+1,lcpRight);
        return longestCommonPrefix(left,right);
    }

    public String longestCommonPrefix(String lcpLeft,String lcpRight) {
        for (int i=0;i<Math.min(lcpLeft.length(),lcpRight.length());i++){
            if(lcpLeft.charAt(i)!=lcpRight.charAt(i)){
                return lcpLeft.substring(0,i);
            }
        }
        return lcpLeft.substring(0,Math.min(lcpLeft.length(),lcpRight.length()));
    }



    public static void main(String[] args) {
        String[] str = new String[]{"flower","flow","flight"};
        System.out.println( new Code14().longestCommonPrefix(str));

    }
}
